class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> deque;
        vector<int> ret(n - k + 1);

        for(int i = 0; i < k; ++i)
        {
            while(!deque.empty() && deque.back() < nums[i])
            {
                deque.pop_back();
            }
            deque.push_back(nums[i]);
        }
        ret[0] = deque.front();

        for(int i = k; i < n; ++i)
        {
            if(deque.front() == nums[i - k])
                deque.pop_front();

            while(!deque.empty() && deque.back() < nums[i])
            {
                deque.pop_back();
            }
            deque.push_back(nums[i]);

            ret[i - k + 1] = deque.front();
        }
        return ret;
    }
};

/*class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ret;
        priority_queue<pair<int, int>> q;
        for(int i = 0; i < k; ++i)
        {
            q.emplace(nums[i], i);
        }
        ret.emplace_back(q.top().first);

        for(int i = k; i < nums.size(); ++i)
        {
            q.emplace(nums[i], i);
            while(q.top().second <= i - k)
            {
                q.pop();
            }
            ret.emplace_back(q.top().first);
        }
        return ret;
    }
};*/

/*class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ret;
        priority_queue<int> q;
        for(int i = 0; i < k; ++i)
        {
            q.push(nums[i]);
        }
        ret.push_back(q.top());
        q.erase(nums[0]);

        for(int i = k; i < nums.size(); ++i)
        {
            q.push(nums[i]);
            ret.push_back(q.top());
            q.erase(nums[0]);
        }
        return ret;
    }
};*/